<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Simple Continued Fractions</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../internals.html" title="Internal tools">
<link rel="prev" href="cf.html" title="Continued Fraction Evaluation">
<link rel="next" href="centered_continued_fraction.html" title="Centered Continued Fractions">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="centered_continued_fraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.internals.simple_continued_fraction"></a><a class="link" href="simple_continued_fraction.html" title="Simple Continued Fractions">Simple
      Continued Fractions</a>
</h3></div></div></div>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">simple_continued_fraction</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">tools</span> <span class="special">{</span>

<span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">Real</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Z</span> <span class="special">=</span> <span class="identifier">int64_t</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">simple_continued_fraction</span> <span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
    <span class="identifier">simple_continued_fraction</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">x</span><span class="special">);</span>

    <span class="identifier">Real</span> <span class="identifier">khinchin_geometric_mean</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span>

    <span class="identifier">Real</span> <span class="identifier">khinchin_harmonic_mean</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span>

    <span class="keyword">template</span><span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">Z_</span><span class="special">&gt;</span>
    <span class="keyword">friend</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">out</span><span class="special">,</span> <span class="identifier">simple_continued_fraction</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">Z</span><span class="special">&gt;&amp;</span> <span class="identifier">scf</span><span class="special">);</span>
<span class="special">};</span>
<span class="special">}</span>
</pre>
<p>
        The <code class="computeroutput"><span class="identifier">simple_continued_fraction</span></code>
        class provided by Boost affords the ability to convert a floating point number
        into a simple continued fraction. In addition, we can answer a few questions
        about the number in question using this representation.
      </p>
<p>
        Here's a minimal working example:
      </p>
<pre class="programlisting"><span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">constants</span><span class="special">::</span><span class="identifier">pi</span><span class="special">;</span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">tools</span><span class="special">::</span><span class="identifier">simple_continued_fraction</span><span class="special">;</span>
<span class="keyword">auto</span> <span class="identifier">cfrac</span> <span class="special">=</span> <span class="identifier">simple_continued_fraction</span><span class="special">(</span><span class="identifier">pi</span><span class="special">&lt;</span><span class="keyword">long</span> <span class="keyword">double</span><span class="special">&gt;());</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="string">"π ≈ "</span> <span class="special">&lt;&lt;</span> <span class="identifier">cfrac</span> <span class="special">&lt;&lt;</span> <span class="string">"\n"</span><span class="special">;</span>
<span class="comment">// Prints:</span>
<span class="comment">// π ≈ [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2]</span>
</pre>
<p>
        The class computes partial denominators while simultaneously computing convergents
        with the modified Lentz's algorithm. Once a convergent is within a few ulps
        of the input value, the computation stops.
      </p>
<p>
        Note that every floating point number is a rational number, and this exact
        rational can be exactly converted to a finite continued fraction. This is
        perfectly sensible behavior, but we do not do it here. This is because when
        examining known values like π, it creates a large number of incorrect partial
        denominators, even if every bit of the binary representation is correct.
      </p>
<p>
        It may be the case the a few incorrect partial convergents is harmless, but
        we compute continued fractions because we would like to do something with
        them. One sensible thing to do it to ask whether the number is in some sense
        "random"; a question that can be partially answered by computing
        the Khinchin geometric mean
      </p>
<p>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/khinchin_geometric.svg" width="173" height="22"></object></span>
      </p>
<p>
        and Khinchin harmonic mean
      </p>
<p>
        <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/khinchin_harmonic.svg" width="153" height="40"></object></span>
      </p>
<p>
        If these approach Khinchin's constant <span class="emphasis"><em>K</em></span><sub>0</sub> and <span class="emphasis"><em>K</em></span><sub>-1</sub> as
        the number of partial denominators goes to infinity, then our number is "uninteresting"
        with respect to the characterization. These violations are washed out if
        too many incorrect partial denominators are included in the expansion.
      </p>
<p>
        Note: The convergence of these means to the Khinchin limit is exceedingly
        slow; we've used 30,000 decimal digits of π and only found two digits of
        agreement with <span class="emphasis"><em>K</em></span><sub>0</sub>. However, clear violations of are
        obvious, such as the continued fraction expansion of √2, whose Khinchin
        geometric mean is precisely 2.
      </p>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="centered_continued_fraction.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
